import java.util.LinkedList;

import entity.board;
import entity.moveDirection;
import entity.state;
import DataStructure.node;
import DataStructure.queue;

public class BFS {
	private queue open;
	private queue closed;
	private board b;
	private node resultNode;

	/*
	 * constructors
	 */
	public BFS() {
		b = txtIO.readFile("input.txt");
		open = new queue();
		closed = new queue();
	}
	public BFS(String fileName) {
		b = txtIO.readFile(fileName);
		open = new queue();
		closed = new queue();
	}
	public BFS(board b){
		this.b=b;
		open = new queue();
		closed = new queue();
	}

	/*
	 * Return if the state of the given node matches the goal. 
	 */
	private boolean isGoal(node node) {
		state s = node.getS();
		if (s.getAx() == s.getBx() && s.getAy() == s.getBy())
			return true;
		else
			return false;
	}

	/*
	 * Search for the solution using BFS method.
	 * If found,return the final node, or return null.
	 * We can use the node's 'parent' information to get
	 * the movement path which means to the solution.
	 */
	public node search() {
		node currentNode = null;
		queue children = new queue();
		if (b == null) {
			System.out.println("Initialization FAILED!");
			return null;
		}
		open.in(new node(b.getCurrentState(), 0, 0, null));
		while (true) {
			if (open.isEmpty()) {
				return null;
			}
			currentNode = open.out();
			if (isGoal(currentNode)) {
				resultNode = currentNode;
				return currentNode;
			}
			children = expand(currentNode);
			while (!children.isEmpty()) {
				node child = children.out();
				int indexOfOpen = open.contains(child);
				int indexOfClosed = closed.contains(child);
				if (indexOfOpen == -1 && indexOfClosed == -1) {
					open.in(child);
				}
			}
			closed.in(currentNode);
		}

	}

	/* Find all the possible next states by moving the agent along four directions
	 * from the given node's state.If one next state is available, wrap it to a 
	 * node with the depth data.Then insert it into the children queue.
	 * Return the children queue.
	 */
	private queue expand(node currentNode) {
		queue children = new queue();
		b.setSate(currentNode.getS());
		int UPCost = b.getA().moveWithAnother(moveDirection.UP, b.getB());
		if (UPCost > 0) {
			state newState = b.getCurrentState();
			node newNode = new node(newState, 0, currentNode.getDepth() + 1,
					currentNode);
			children.in(newNode);
		}
		b.setSate(currentNode.getS());
		int RIGHTCost = b.getA().moveWithAnother(moveDirection.RIGHT, b.getB());
		if (RIGHTCost > 0) {
			state newState = b.getCurrentState();
			node newNode = new node(newState, 0, currentNode.getDepth() + 1,
					currentNode);
			children.in(newNode);
		}

		b.setSate(currentNode.getS());
		int DOWNCost = b.getA().moveWithAnother(moveDirection.DOWN, b.getB());
		if (DOWNCost > 0) {
			state newState = b.getCurrentState();
			node newNode = new node(newState, 0, currentNode.getDepth() + 1,
					currentNode);
			children.in(newNode);
		}

		b.setSate(currentNode.getS());
		int LEFTCost = b.getA().moveWithAnother(moveDirection.LEFT, b.getB());
		if (LEFTCost > 0) {
			state newState = b.getCurrentState();
			node newNode = new node(newState, 0, currentNode.getDepth() + 1,
					currentNode);
			children.in(newNode);
		}

		return children;
	}
	
	/*
	 * use the node's 'parent' information to get
	 * the movement path which means to the solution.
	 */
	public String getPath(node currentNode) {
		LinkedList<String> pathList = new LinkedList<String>();
		while (currentNode.getParent() != null) {
			pathList.offer(currentNode.getS().getAx() + " "
					+ currentNode.getS().getAy() + "\r\n");
			currentNode = currentNode.getParent();
		}
		pathList.offer(currentNode.getS().getAx() + " "
				+ currentNode.getS().getAy() + "\r\n");
		String path = "";
		for (int i = pathList.size() - 1; i >= 0; i--) {
			path += pathList.get(i);
		}
		return path;
	}

	/*
	 * Generate the result String.
	 */
	public String getResultString() {
		String result = "";
		if (resultNode != null) {
			result += resultNode.getDepth();
			result += "\r\n";
			result += getPath(resultNode);
		}else{
			result="-1\r\n";
		}
		return result;
	}
	
	public void writeToTXT(String fileName) {
		if (resultNode != null) {
			txtIO.writeFile(fileName, getResultString());
		}
	}
	
	public void appendToTXT(String fileName){
		if (resultNode != null) {
			txtIO.appendFile(fileName, getResultString());
		}
	}
}
